package com.atguigui.leetcode;

/**
 * 324.摆动排序 II
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by WJX on 2022/6/28 11:14
 */
public class P324WiggleSortIi {
    public static void main(String[] args) {
        Solution solution = new P324WiggleSortIi().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public void wiggleSort(int[] nums) {
            int[] arr = new int[5001];

            //num对应的所在桶中的位置排序，并标记为1，对应的位置就是该数的值
            for (int num : nums) {
                arr[num]++;
            }

            int n = nums.length;
            //最大为5000
            int r = 5000;

            //放大数
            for (int i = 1; i < n; i += 2) {
                //从大到小排除为0的数   r记录当前的数
                while (arr[r] == 0) r--;
                //取出一个数
                arr[r]--;
                //把r放入到数组中
                nums[i] = r;
            }

            //放小数
            for (int i = 0; i < n; i += 2) {
                while (arr[r] == 0) r--;
                arr[r]--;
                nums[i] = r;
            }

        }
    }
}
